Spurred by technological advances, the telecommunications industry has experienced tremendous growth over the last decade. The advances in processing power of desktop computers and the decrease in applications response times fostered corresponding improvements in the network infrastructure. The new bandwidth consuming applications supported the network traffic growth and the rapid change in equipment utilization confront the network providers with the issue of whether the network has adequate capacity to support the current and the future traffic requirements.
In any traffic and/or network engineering task, more knowledge about the network can only be beneficial. Specific applications require for example knowledge of how much traffic goes from a site A to a site B, how much traffic does a particular customer sends from site A to B, where is the hot spot in the network, or how much capacity needs to be added and where. Information about network behaviour under specific conditions is also useful. For example, a network provider may optimize network performance based on the knowledge of how much traffic has to be moved if a link fails, what happens if traffic between two points is moved from a link to another, is most traffic originating in a sub-network (autonomous system, country, or company) staying in that sub-network or not, etc. This knowledge is used generally for routing path calculations, load balancing, etc.
Network engineering tools were designed for handling these issues created by the increases in traffic demands or changes in the existing demands and determining the necessary expansion or modification to the network to support the projected traffic. These tools generally aid in revising network designs and routing schemes to avoid traffic bottlenecks, enable differential pricing of services, etc. However, all these tools require knowledge of traffic statistics, and more specifically of the real time source-destination traffic demands.
A way of keeping these statistics for a packet based network is to look at each packet and record its source and destination. However, this method requires huge tables for recording this information. Furthermore, if what is desired is a source to destination traffic matrix for a subset of the network, then the ingress into the subset and the egress from the subset will not be available without looking at the source and destination addresses and then determining the path the packet would take as indicated by the routing information. This would be infeasible for large networks and large numbers of packets.
It is also known to organize the traffic statistics into a “traffic matrix”. A traffic matrix is typically expressed as the total bytes of data or the total number of packets or connections between all of the source-destination pairs of nodes. While the current routers are able to measure the counts for the incoming and outgoing traffic at each interface (incoming and outgoing links), it is generally impossible to derive the traffic matrix from the link counts with mathematical certainty. The best that can be done is to make a probabilistic inference concerning the traffic matrix from the observed link traffic.
AT&T proposed to infer traffic matrices from the available measurements of link loads, by combining two known models, namely the gravity model with the tomographic model. The gravity model assumes that the traffic between the sites is proportional to the traffic at each site on per peer basis (as opposed to per router basis) for the outbound traffic, and that there is no systematic difference between the traffic in different locations. The tomographic model applies link constraints based on models. The combination of these models reduces the problem size for large networks and provides more accurate results that the gravity and tomographic models separately.
However, the tomo-gravity method does not allow for easy specification of arbitrary constraints, such as knowing that if a link is twice the speed of another, it probably has roughly twice the traffic. Also, this method is based on assuming that the traffic follows the ‘gravity’ model, which can not be assumed in practice.
The prior art techniques described above, such as monitoring all packets and gravity, tomographic approach and tomo-gravity, are not satisfactory for large traffic volumes and rely on unrealistic assumptions, respectively. On the other hand, it is essential to provide tools and techniques for traffic engineering in modem communication networks, particularly for estimating traffic patterns (characteristics), e.g. traffic volumes, hotspots, effects of failures, etc.